package com.future;

import com.future.util.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * Description: 450. 删除二叉搜索树中的节点
 * <p>
 * 输入：root = [5,3,6,2,4,null,7], key = 3
 * 输出：[5,4,6,2,null,null,7]
 *
 * @author weiruibai.vendor
 * Date: 2022/12/29 15:15
 */
public class Solution_450 {

    private static Solution_450 instance = new Solution_450();

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);

        root.right = new TreeNode(6);
        root.right.right = new TreeNode(7);

        int key = 5;
        instance.deleteNode(root, key);
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        Map<Integer, TreeNode> map = new HashMap<>();
        Map<TreeNode, TreeNode> childParentMap = new HashMap<>();
        childParentMap.put(root, null);
        buildMap(root, map, childParentMap);
        TreeNode removeNode = map.get(key);
        // 找不到
        if (removeNode == null) {
            return root;
        }
        //  只有一个节点且删除的是该节点
        if (map.size() == 1) {
            return null;
        }
        /**
         * 移除节点的父亲节点
         */
        TreeNode parent = childParentMap.get(removeNode);
        if (parent == null) {
            // 删除的是根节点
            TreeNode left = removeNode.left;
            if (removeNode.right == null) {
                // 没有右子树
                root = left;
            } else {
                root = getRightMostLeftNode(removeNode.right);
                if (root != removeNode.right) {
                    parent = childParentMap.get(root);
                    if (parent.left == root) {
                        parent.left = null;
                    } else {
                        parent.right = null;
                    }
                    root.right = removeNode.right;
                }
                root.left = removeNode.left;
            }
        } else if (removeNode.left == null && removeNode.right == null) {
            // 恰好是叶子节点，直接移除
            if (parent.left == removeNode) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        } else if (removeNode.right == null) {
            // 没有右节点
            if (parent.left == removeNode) {
                parent.left = removeNode.left;
            } else {
                parent.right = removeNode.left;
            }
        } else {
            if (parent.left == removeNode) {
                parent.left = removeNode.right;
            } else {
                parent.right = removeNode.right;
            }
            // 获取removeNode右子树的最左节点
            if (removeNode.left != null) {
                TreeNode rightMostLeftNode = getRightMostLeftNode(removeNode.right);
                rightMostLeftNode.left = removeNode.left;
            }
        }
        return root;
    }

    private TreeNode getRightMostLeftNode(TreeNode removeNode) {
        if (removeNode == null) {
            return null;
        }
        while (removeNode.left != null) {
            removeNode = removeNode.left;
        }
        return removeNode;
    }

    private void buildMap(TreeNode root, Map<Integer, TreeNode> map, Map<TreeNode, TreeNode> childParentMap) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            childParentMap.put(root.left, root);
        }
        if (root.right != null) {
            childParentMap.put(root.right, root);
        }
        map.put(root.val, root);
        buildMap(root.left, map, childParentMap);
        buildMap(root.right, map, childParentMap);
    }
}
